// https://www.lintcode.com/problem/kth-prime-number/

public class Solution {
    /**
     * @param n: the number
     * @return: the rank of the number
     */
    public int kthPrime(int n) {
        // write your code here
        int ret = 0;
        int[] flags = new int[n + 1];
        Arrays.fill(flags, 0); // 0代表质数
        for (int i = 2; i <= n; ++i) {
            if (flags[i] == 0) {
                ++ret;
            }
            for (int j = 2; (i * j) < n; ++j) {
                flags[i * j] = 1;
            }
        }
        return ret;
    }
}